Dvojna Vrsta

Avtor

Avtor: Helena Angelski
DIRI, Študijsko leto 2004/05
 

Viri:

  1. Michael T. Goodrich, Roberto Tamassia: Data Structures and Algorithms in Java. John Wiley & Sons, NY 2001. (str.: 149-155, 166-167 oz. 166-172)
  2. Jernej Kozak: Podatkovne strukture in Algoritmi. Društvo MFA SRS, LJ 1986. (str.: 32-39)

Kratek opis problema

  1. Kaj je enojna vrsta?
    - za lažje razumevanje podatkovne strukture dvojna vrsta najprej razložimo strukturo (enojna) vrsta: je podatkovna struktura, v katero lahko vstavljamo elemente na enem koncu, na drugem pa jih lahko jemljemo ven, in sicer v istem vrstnem redu kot so vanjo prihajali.
  2. Kaj je dvojna vrsta?
    - opis podatkovne strukture: dvojna vrsta je struktura, ki poleg običajnega vstavljanja in brisanja na začetku vrste podpira tudi vstavljanje in brisanje elementov na koncu vrste.
  3. Implementacija podatkovne strukture dvojna vrsta:
    - zapis razreda DvojnaVrsta v programskem jeziku Java s potrebnimi konstruktorji, get/set metodami in metodo toString, ki morajo delovati na način, kot predvideva definicija podatkovne strukture. Glede na to, da obstaja več možnosti predstavitve strukture, se lahko sami odločimo, v kakšni obliki jo bomo predstavili in kakšne vrednosti bomo v njej shranjevali.

Opis podatkovne strukture

Implementacija podatkovne strukture

Dvojno vrsto smo implementirali kot tabelo, v kateri hranimo cela števila. Pomembno je, da je vrsta predstavljena kot krožna tabela, ki nam omogoča na koncu in začetku vrste dostop do elementov po modulu velikosti tabele. V vrsti lahko hranimo en element manj kot je njena velikost, zato da lahko zaradi krožnega delovanja metod ločimo med polno in prazno vrsto.

SPREMENLJIVKE: V razredu definiramo naslednje spremenljivke, do katerih uporabnik nima direktnega dostopa:
protected int z; //indeks zadnjega prostega mesta pred začetkom vrste, (začetek vrste - 1)
protected int k; //indeks zadnjega mesta v vrsti, konec vrste
protected int[] t; //tabela celih števil, kamor bomo vstavljali elemente vrste
protected int vel = 10; //velikost tabele - vrednost ji priredimo takoj

KONSTRUKTORJI: V razredu so uporabljeni trije konstruktorji, ki pripravijo vrsto:
  1. splošni konstruktor: pripravi prazno vrsto z 10 mesti za vstavljanje
  2. konstruktor: pripravi prazno vrsto željene velikosti
  3. konstruktor: pripravi vrsto, ki vsebuje elemente iz dane tabele. Velikost te vrste je določena s prvim konstruktorjem.
get/set METODE: V razredu potrebujemo naslednje metode, ki so glede na implementacijo strukture kot tabele natačneje opisane v enem od prejšnjih poglavij: Predstavitev dvojne vrste s tabelo
METODA toString: izpiše vrsto oz. elemente v vrsti

RAZRED: DvojnaVrsta

Testiranje razreda DvojnaVrsta

Dodatni komentarji

Časovna zahtevnost operacij:

V opisu predstavitve vrste s tabelo je že nakazana časovna zahtevnost operacij dvojne vrste. Pri operacijah težimo k temu, da bi bilo izvajanje operacij konstantno, neodvisno od števila elementov v tabeli, se pravi O(1) in ne O(n).

S krožno predstavitvijo vrste dosežemo, da pri brisanju elementov z začetka vrste (operacija odstraniZacetek), ni potrebno elemente prestavljati za eno mesto nazaj (tu bi bila časovna odvisnost izvajanja operacije odvisna od št. elementov), da bi zapolnili manjkajoči prostor. Kar prestavimo, je le indeks, ki kaže na eno mesto pred začetkom vrste. Prestavljanje tega indeksa pa je neodvisno od števila elementov v tabeli in na tak nacin je časovna odvisnost izvajanja operacije konstantna.

Podobno je z operacijo vstaviZacetek – namesto prestavljanja vseh elementov za enega naprej, da bi dobili prosto mesto na začetku, samo prestavimo prej omenjeni indeks, da kaže na eno mesto nazaj. Izvajanje operacije je zopet konstantno.

Pri ostalih operacijah - vstaviKonec, odstraniKonec, konec, zacetek, velikost se ta problem prestavljanja elementov ne pojavlja - element enostavno odstranimo, pobrišemo oz. vrnemo; samo spreminjamo vrednost indeksov, ki označujeta konec in eno mesto pred začetkom vrste, s katerima tudi ves čas operiramo. Te operacije so tako zopet neodvisne od št. elementov v tabeli.

Edina operacija, ki pa je odvisna od št. elementov v tabeli, je operacija toString, kjer pa to drugače ne gre - vsak element pač moramo izpisati posebej, tako da smo odvisni od št. elementov v tabeli.

Prostorska zahtevnost operacij:

Je prav tako konstantna, saj poleg dveh spremenljivk, kjer hranimo velikost tabele in seveda samo tabelo, za vsako vrsto potrebujemo prostor le še za dve dodatni spremenljivki - indeks konca in indeks zadnjega prostega mesta pred začetkom vrste. Število spremenljivk, ki jih potrebujemo za katerokoli vrsto, je tako neodvisno od števila elementov v tabeli.